package leetcode;

/**
 * description:
 * author:zt
 * date:2021-08-05
 */
//链表的快排
public class quicksort {
    public ListNode sortList(ListNode head) {
        quickSort(head,null);
        return head;
    }
    public void quickSort(ListNode head,ListNode end){
        if (head!=end){
            ListNode node = partition(head, end);
            quickSort(head,node);
            quickSort(node.next,end);
        }
    }
    public ListNode partition(ListNode head,ListNode end){
        ListNode p1 = head, p2 = head.next;
        while (p2!=end){
            if (p2.val<head.val){
                p1 = p1.next;

                int tmp = p2.val;
                p2.val = p1.val;
                p1.val = tmp;
            }
            p2 = p2.next;
        }
        if (p1!=end){
            int tmp = p1.val;
            p1.val = head.val;
            head.val = tmp;
        }
        return p1;
    }

}
